package com.eistert.java.algorithm.prim;

/**
 * @Description: ???????
 * @Author: ai
 * @create: 2023-04-27 10:25
 */
public class PrimAlgoithm {

    /**
     * ??·????
     * 1)????????? 7 ?????(A, B, C, D, E, F, G) ???????????·?? 7 ????????
     * 2)?????????????ñ?????(?) ?????? A ?C B  ???? 5 ????
     * ????????·???????????????????????????????·?????????
     *
     * ?·
     * 3)?? 10 ????????????????????????????????.
     * ??????·??????????????????·???????ÿ??·?????????????????????.
     */

    /**??·?????????????????????????
     * ?????????????????(Minimum Cost Spanning Tree)????? MST??
     * ????????????????????,??????????????,??????????????????????,????????????
     *N ??????????? N-1 ????,???????????,N-1 ??????????
     *
     *??????????????????????????????³???????
     */

    /**
     * ??????????£?
     * 1)?? G=(V,E)?????????T=(U,D)?????????????V,U ????????E,D ????????
     * <p>
     * 2)??????? u ???????????????????????? V ????????? u ?????? U ????????? v ?? visited[u]=1??
     * <p>
     * 3)?????? U ????? ui ???? V-U ?????? vj ?????????????????????????????
     * <p>
     * ??????????·???????? vj ?????? U ????????ui,vj???????? D ?????? visited[vj]=1
     * <p>
     * 4)???????????? U ?? V ????????????????????????????? D ???? n-1 ????
     */

    public static void main(String[] args) {
        //???????????? ok
        char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};

        int verxs = data.length;
        //???????????ö????????,10000 ?????????????????????
        int[][] weight = new int[][]{
                {10000, 5, 7, 10000, 10000, 10000, 2},
                {5, 10000, 10000, 9, 10000, 10000, 3},
                {7, 10000, 10000, 10000, 8, 10000, 10000},
                {10000, 9, 10000, 10000, 10000, 4, 10000},
                {10000, 10000, 8, 10000, 10000, 5, 4},
                {10000, 10000, 10000, 4, 5, 10000, 6},
                {2, 3, 10000, 10000, 4, 6, 10000},};

        // ????MGraph????
        MGraph graph = new MGraph(verxs);

        // ???????MinTree????
        MinTree minTree = new MinTree();
        minTree.createGraph(graph, verxs, data, weight);

        // ???
        minTree.showGraph(graph);

        // ???????????
        minTree.prim(graph, 1);
    }


}
